#ifndef _BASELIB_FASTTRIE_
#define _BASELIB_FASTTRIE_

#include <limits>
#include <vector>

template<class TChar, class TStateType, class TStateData>
class TFastTrie {
public:

    typedef TChar       TInnerChar;
    typedef TStateType  TInnerStateType;
    typedef TStateData  TInnerStateData;
    
    
    static const TStateType     kStartState = 0;
    static const TStateType     kInvalidState;
    static const TChar          kMinChar;
    static const TChar          kMaxChar;

    TFastTrie()
    : StatesData(1, TStateFullData(false))
    , Transitions(kSize, kInvalidState) //add empty transitions from start state
    {}

    TStateType  Go( TStateType startState, TChar symbol ) const
    {
        TStateType  ret(kInvalidState);
        unsigned int    pos(startState * kSize + (symbol - kMinChar));
        if (Transitions.size() > pos) {
            ret =   Transitions[pos];
        }
        return ret;
    }

    TStateType  AddTransition( TStateType startState
                             , TChar symbol
                             , bool isEnd = false
                             , const TStateData& data = TStateData() )
    {
        
        unsigned int    pos(startState * kSize + (symbol - kMinChar));
        
        if (Transitions.size() <= pos) {
            //try to add transition for non-existent state
            return kInvalidState;            
        }

        TStateType  ret(Transitions[pos]);

        if (kInvalidState == ret) {
            ret =   StatesData.size();
            if (std::numeric_limits<TStateType>::max() == ret) {
                //reach limit of TStateType
                return kInvalidState;
            }
            Transitions[pos] =  ret;
            
            StatesData.push_back(TStateFullData(false));
            Transitions.resize(Transitions.size() + kSize, kInvalidState);                        
        }

        TStateFullData& stateData(StatesData[ret]);

        if (isEnd) {
            stateData.IsEnd =   isEnd;
        }

        stateData.Data  =   data;

        return ret;
    }

    TStateData* GetStateData( TStateType state )
    {
        if (StatesData.size() <= state) {
            return 0;
        }

        return &(StatesData[state].Data);
    }

    bool IsStateAccepted( TStateType state )const
    {
        if (StatesData.size() <= state) {
            return false;
        }

        return StatesData[state].IsEnd;
    }

private:
    static const unsigned int   kSize;    

    struct TStateFullData {
        TStateFullData( bool isEnd, TStateData data = TStateData())
        : Data(data)
        , IsEnd(isEnd)
        {}
        
        TStateData  Data;
        bool        IsEnd;
    };

    typedef std::vector<TStateFullData> TData;
    typedef std::vector<TStateType>     TTransitions;

    TData           StatesData;
    TTransitions    Transitions;    
};

template<class TChar, class TStateType, class TStateData>
const TChar TFastTrie<TChar, TStateType, TStateData>::kMinChar              =   std::numeric_limits<TChar>::min();

template<class TChar, class TStateType, class TStateData>
const TChar TFastTrie<TChar, TStateType, TStateData>::kMaxChar              =   std::numeric_limits<TChar>::max();

template<class TChar, class TStateType, class TStateData>
const unsigned int TFastTrie<TChar, TStateType, TStateData>::kSize          =   kMaxChar - kMinChar + 1;

template<class TChar, class TStateType, class TStateData>
const TStateType TFastTrie<TChar, TStateType, TStateData>::kInvalidState    =   std::numeric_limits<TStateType>::max();

template<class TTrie, class Iterator>
bool addChain( TTrie& trie
             , Iterator begin
             , Iterator preEnd // ++preEnd == end
             , typename TTrie::TInnerStateData data )
{
    typename TTrie::TInnerStateType state(TTrie::kStartState);
    while ((state != TTrie::kInvalidState) and (begin != preEnd)) {
        state   =   trie.AddTransition(state, *begin);
        ++begin;
    }

    if (TTrie::kInvalidState != state) {
        state   =   trie.AddTransition(state, *begin, true, data);
    }

    return TTrie::kInvalidState != state;
}

template<class TTrie, class Iterator>
typename TTrie::TInnerStateType checkChain( const TTrie& trie
                                          , Iterator begin
                                          , Iterator end )
{
    typename TTrie::TInnerStateType state(TTrie::kStartState);
    while ((state != TTrie::kInvalidState) and (begin != end)) {
        state   =   trie.Go(state, *begin);
        ++begin;
    }

    return state;
}



#endif
